package mo.tags.stack;

import java.util.Stack;

public class L316 {

    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c-'a']++;
        }
        boolean[] instack = new boolean[26];
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            count[c-'a']--;
            if (instack[c-'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > c) {
                if (count[stack.peek()-'a'] == 0) {
                    break;
                }
                char p = stack.pop();
                instack[p-'a'] = false;
            }
            stack.push(c);
            instack[c-'a'] = true;
        }

        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        return builder.reverse().toString();
    }

}
